namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0010. 正则表达式匹配")]
    public class No0010_IsMatch : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(IsMatch, "", ".*", true);
            Assert.TestExe(IsMatch, "aa", "a", false);
            Assert.TestExe(IsMatch, "aa", "a*", true);
            Assert.TestExe(IsMatch, "aa", ".*", true);
            Assert.TestExe(IsMatch, "aab", "c*a*b", true);
            Assert.TestExe(IsMatch, "mississippi", "mis*is*p*.", false);
            Assert.TestExe(IsMatch, "mississippi", "mis*is*ip*.", true);
        }

        public bool IsMatch(string s, string p)
        {
            int m = s.Length;
            int n = p.Length;
            bool[,] f = new bool[m + 1, n + 1];
            f[0, 0] = true;
            bool matches(int i, int j)
            {
                if (i == 0)
                {
                    return false;
                }
                if (p[j - 1] == '.')
                {
                    return true;
                }
                return s[i - 1] == p[j - 1];
            };
            for (int i = 0; i <= m; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (p[j - 1] == '*')
                    {
                        f[i, j] = f[i, j - 2];
                        if (matches(i, j - 1))
                        {
                            f[i, j] = f[i, j] || f[i - 1, j];
                        }
                    }
                    else
                    {
                        if (matches(i, j))
                        {
                            f[i, j] = f[i - 1, j - 1];
                        }
                    }
                }
            }
            return f[m, n];
        }
    }
}
